package sort;

import list.LinkedListCreate;
import list.ListNode;

public class ListSort {

	public static void main(String[] args) {
		int[] array = {1,1};
		ListNode head = LinkedListCreate.createList(array);
		head = insertionSortList2(head);
		LinkedListCreate.printList(head);
	}
	// sort the LinkedList
	public ListNode insertionSortList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		// 思想是新建一个链表，将head中的结点逐渐的加入到这个新的链表中
		// 维护一个最小的结点，每次从头顺序查找需要改变位置的结点
		ListNode temp = new ListNode(0);
		ListNode previous = temp; // 将current插入到previous 和previous.next之间
		ListNode current = head; // 需要插入的结点
		ListNode next = null; // 用来暂存cur的next结点
		while (current != null) {
			next = current.next;
			while (previous.next != null && previous.next.val < current.val) {
				previous = previous.next;
			}
			// 将current插入到了新的链表中
			current.next = previous.next;
			previous.next = current;
			// 进行下一次循环
			previous = temp;
			current = next;
		}
		return temp.next;
	}
	//directly sort the list ,doesn't need create a new node
	public static ListNode insertionSortList2(ListNode head){
		if(head == null || head.next == null){
			return head;
		}
		ListNode cur = head.next;  //这个代表的是需要被插入的结点
		ListNode pre = head;   //需要被插入的结点的前一个结点
		while(cur != null){
			if(cur.val >= pre.val){
				pre = cur;
				cur = cur.next;
				continue;
			}
			ListNode minNode = head;  //这个表示的是插入到该结点的前面
			ListNode minPre = head;   //该结点的后面
			while(minNode.val <= cur.val){
				if(minNode == minPre){
					//初始时都是指向的head，所以先移动minNode
					minNode = minNode.next;
				}else{
					minPre = minNode;
					minNode = minNode.next;
				}
			}
			pre.next = cur.next;
			//如果是头结点，处理方式稍有不同
			if(minNode == head){
				cur.next = minNode;
				head = cur;
			}else{
				cur.next = minNode;
				minPre.next = cur;
			}
			cur = pre.next;
		}
		return head;
	}
//	public boolean isHappy(int n) {
//        int slow = n , fast = n;
//        do{
//            slow = digitSquareSum(slow);
//            fast = digitSquareSum(fast);
//            fast = digitSquareSum(fast);
//        }while(slow != fast);
//    }
}
